package com.zyk.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/18 11:52
 */
public class C101 {

    // https://leetcode-cn.com/problems/symmetric-tree/
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return dfs(root.left, root.right);
    }

    public boolean dfs(TreeNode l, TreeNode r) {
        if (l == null && r == null) return true;
        if (l == null || r == null || l.val != r.val) return false;
        return dfs(l.left, r.right) && dfs(l.right, r.left);
    }

    // bfs
    public boolean isSymmetric2(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>(){{ add(root.left); add(root.right); }};
        while (!q.isEmpty()) {
            TreeNode l = q.poll();
            TreeNode r = q.poll();
            if(l==null && r == null) continue;
            if(l==null || r==null || l.val != r.val) return false;
            q.offer(l.left);
            q.offer(r.right);
            q.offer(l.right);
            q.offer(r.left);
        }
        return true;
    }
}
